/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-22
 * Time: 22:19
 */

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        if (len1 + len2 != len3){
            return false;
        }
        // dp[i][j] 表示s1 的前 i 个字母和 s2 的前 j 个字母能否交织成 s3的前 i + j 个字母
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2 ; j++) {
                int index = i + j -1;
                // 只要其中一个 > 0 , 就可以进行判断
                if (i > 0){
                    dp[i][j] = dp[i - 1][j] && (s1.charAt(i - 1) == s3.charAt(index));
                }
                // 注意只要与其中一个能够交织即可, 所以只要已经变为 true 了, 那么就没有必要与 s2 判断了
                if (j > 0 && (!dp[i][j])){
                    dp[i][j] = dp[i][j - 1] && (s2.charAt(j - 1) == s3.charAt(index));
                }
            }
        }
        return dp[len1][len2];
    }
}
